#include <iostream>
#include <iomanip>
using namespace std;

#define MaxVertexNum 10000
#define MaxDistance 6
#define DefaultWeight 1
#define QERROR 0

typedef int Vertex;
typedef int WeightType;

typedef struct ENode *PtrToENode;
struct ENode
{
    Vertex V1, V2;
    WeightType Weight;
};
typedef PtrToENode Edge;

typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode
{
    Vertex AdjV;
    WeightType Weight;
    PtrToAdjVNode Next;
};

typedef struct Vnode
{
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;
struct GNode
{
    int Nv;
    int Ne;
    bool *visited;
    AdjList G;
};
typedef PtrToGNode LGraph;

typedef struct Node *PtrToNode;
struct Node
{
    Vertex Data;
    PtrToNode Next;
};
typedef PtrToNode Position;

struct QNode
{
    Position Front, Rear;
    int MaxSize;
};
typedef struct QNode *Queue;

LGraph CreateGraph(int Nv);
void InsertEdge(LGraph Graph, Edge E);
void BFSToSix(LGraph Graph);
int BFS(LGraph Graph, Vertex v);
Queue CreateQueue(int MaxSize);
bool QIsEmpty(Queue Q);
Vertex DeleteQ(Queue Q);
void AddQ(Queue Q, Vertex v);

int main()
{

    int N, M;
    LGraph Graph;
    Edge E;
    while (1)
    {
        cin >> N;
        cin >> M;
        if (N==0&&M==0)
            break;
        Graph = CreateGraph(N);
        E = new ENode;
        for (int i = 0; i < M; i++)
        {
            cin >> E->V1;
            cin >> E->V2;
            E->Weight = DefaultWeight;
            InsertEdge(Graph, E);
        }
        BFSToSix(Graph);
    }
    return 0;
}

void BFSToSix(LGraph Graph)
{
    int SixVertexNum;
    float percent;
    if (Graph->Nv != 0)
    {
        for (Vertex v = 1; v < Graph->Nv; v++)
        {

            SixVertexNum = BFS(Graph, v) + 1;

            percent = float(SixVertexNum) / float(Graph->Nv - 1);
            cout << v << ":"
                 << " ";
            cout << fixed << setprecision(2) << percent * 100 << "%" << endl;

            for (int i = 0; i < Graph->Nv; i++)
                Graph->visited[i] = false;
        }
    }
}

int BFS(LGraph Graph, Vertex v)
{
    PtrToAdjVNode w;
    int D = 0;
    int SixVertexNum = 0;
    Queue Q;

    Q = CreateQueue(MaxVertexNum); // 创建队列

    Graph->visited[v] = true;
    AddQ(Q, v);
    AddQ(Q, 0); // 插入队列中的0，用于表示新的一层的开始
    ++D;
    while (!QIsEmpty(Q))
    {
        v = DeleteQ(Q);
        if (v == 0 && D >= MaxDistance)
            break; // 表示层数已超过6
        if (v == 0 && D < MaxDistance)
        { // 层数还未超过6
            AddQ(Q, 0);
            ++D;
            continue;
        }
        for (w = Graph->G[v].FirstEdge; w != NULL; w = w->Next)
        {

            if (!Graph->visited[w->AdjV])
            {
                Graph->visited[w->AdjV] = true;
                AddQ(Q, w->AdjV);
                ++SixVertexNum;
            }
        }
    }
    return SixVertexNum;
}

void InsertEdge(LGraph Graph, Edge E)
{
    PtrToAdjVNode NewNode;

    ++Graph->Ne;

    NewNode = new AdjVNode;
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;

    NewNode = new AdjVNode;
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

LGraph CreateGraph(int N)
{
    LGraph Graph;

    Graph = new GNode;
    Graph->Nv = N + 1; // 结点从1开始
    Graph->Ne = 0;
    Graph->visited = new bool[N + 1];

    for (int i = 1; i < Graph->Nv; i++)
        Graph->visited[i] = false;

    for (int v = 1; v < Graph->Nv; v++)
        Graph->G[v].FirstEdge = NULL;

    return Graph;
}

Queue CreateQueue(int MaxSize)
{
    Queue Q;
    Q = new QNode;
    Q->Front = Q->Rear = NULL;
    Q->MaxSize = MaxSize;
    return Q;
}

bool QIsEmpty(Queue Q)
{
    return (Q->Front == NULL);
}

void AddQ(Queue Q, Vertex v)
{
    Position NewNode;
    NewNode = new Node;
    NewNode->Data = v;
    NewNode->Next = NULL;

    if (QIsEmpty(Q))
    {
        Q->Front = NewNode;
        Q->Rear = NewNode;
    }
    else
    {
        Q->Rear->Next = NewNode;
        Q->Rear = NewNode;
    }
}

Vertex DeleteQ(Queue Q)
{
    Position FrontNode;
    Vertex FrontData;

    if (QIsEmpty(Q))
    {
        return QERROR;
    }
    else
    {
        FrontNode = Q->Front;
        if (Q->Front == Q->Rear)
            Q->Front = Q->Rear = NULL;
        else
            Q->Front = Q->Front->Next;

        FrontData = FrontNode->Data;
        delete FrontNode;
        return FrontData;
    }
}